package com.example.question.list.list2;

import com.example.question.list.list1.List;
import com.example.question.list.list1.ListNode;

import java.util.Stack;

/**
 * @Date 2023-07-07
 * @Author Jonathan
 */
public class Code01_234 {
    public static void main(String[] args) {
        ListNode listNode = List.createList(new int[]{1, 0, 0, 1});
        Code01_234 code = new Code01_234();
        boolean palindrome = code.isPalindrome(listNode);
        System.out.println(palindrome);

    }


    public boolean isPalindrome(ListNode head) {
        if (head == null || head.next == null) {
            return true;
        }
        int length = 0;
        ListNode cur = head;
        while (cur != null) {
            length++;
            cur = cur.next;
        }

        Stack<Integer> stack = new Stack<>();
        cur = head;
        for (int i = 0; i < length / 2; i++) {
            stack.push(cur.val);
            cur = cur.next;
        }
        // 奇数的时候是中点  还需要往下走一个
        if (length % 2 == 1) {
            cur = cur.next;
        }
        while (!stack.isEmpty()) {
            if (stack.pop() != cur.val) {
                return false;
            }
            cur = cur.next;
        }
        return true;
    }

    /**
     * 扣边界
     *
     * @param head
     * @return
     */
    public boolean isPalindrome1(ListNode head) {
        if (head == null || head.next == null) {
            return true;
        }
        // 统计长度
        int length = 0;
        ListNode cur = head;
        while (cur != null) {
            length++;
            cur = cur.next;
        }
        if (length == 2) {
            return head.next.val == head.val;
        }
        // 取一半
        int half = length / 2;
        cur = head;
        int index = 1;
        ListNode firstPartTail = null;
        while (index <= half) {
            if (index == half) {
                firstPartTail = cur;
            }
            cur = cur.next;
            index++;
        }
        firstPartTail.next = null;
        // 奇数的时候是中点  偶数的时候是下中点
        ListNode secondPartHead;
        if (length % 2 == 0) {
            secondPartHead = cur;
        } else {
            secondPartHead = cur.next;
        }
        ListNode reverse = reverse(head);
        while (reverse != null) {
            if (reverse.val != secondPartHead.val) {
                return false;
            }
            reverse = reverse.next;
            secondPartHead = secondPartHead.next;
        }
        System.out.println(cur);

        return true;
    }

    private ListNode reverse(ListNode head) {
        if (head.next == null) {
            return head;
        }
        ListNode ret = reverse(head.next);
        head.next.next = head;
        head.next = null;
        return ret;
    }


}
